package erfgame.core.world.terrain.factory.j3d;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.logging.Logger;

import javax.media.j3d.Appearance;
import javax.media.j3d.BoundingBox;
import javax.media.j3d.Bounds;
import javax.media.j3d.BranchGroup;
import javax.media.j3d.Canvas3D;
import javax.media.j3d.Geometry;
import javax.media.j3d.GeometryArray;
import javax.media.j3d.Node;
import javax.media.j3d.PickInfo;
import javax.media.j3d.PickRay;
import javax.media.j3d.PolygonAttributes;
import javax.media.j3d.SceneGraphObject;
import javax.media.j3d.Shape3D;
import javax.media.j3d.Transform3D;
import javax.media.j3d.TransformGroup;
import javax.media.j3d.PickInfo.IntersectionInfo;
import javax.swing.SwingUtilities;
import javax.vecmath.Point3d;
import javax.vecmath.Point3f;
import javax.vecmath.Vector3d;
import javax.vecmath.Vector3f;

import com.sun.j3d.utils.geometry.GeometryInfo;
import com.sun.j3d.utils.universe.SimpleUniverse;

import erfgame.core.Dimensions3D;
import erfgame.core.OperationProgress;
import erfgame.core.OperationProgressEvent;
import erfgame.core.OperationProgressListener;
import erfgame.core.Pair;
import erfgame.core.Rotation;
import erfgame.core.j3d.BranchGroupFactory;
import erfgame.core.world.terrain.MaterialType;
import erfgame.core.world.terrain.TerrainConstants;
import erfgame.core.world.terrain.TerrainUpdate;
import erfgame.core.world.terrain.TerrainUpdateByMaterialTypeBoundsAndRotationFactory;
import erfgame.core.world.terrain.TerrainUpdateGroup;

public class Shape3DTerrainUpdateByMaterialTypeBoundsAndRotationFactory
		implements TerrainUpdateByMaterialTypeBoundsAndRotationFactory {
	
	private static final Logger log = Logger.getLogger( Shape3DTerrainUpdateByMaterialTypeBoundsAndRotationFactory.class.getName());
	
	/**
	 * never make this less than two as every second voxel is removed when viewing front-on
	 */
	private static final int DEFAULT_WAFER_THICKNESS = 4;
	
	private static final int MIN_COMMON_VERTEXES = 1;
	
	private int waferThickness = DEFAULT_WAFER_THICKNESS;
	
	private static final int PROGRESS_NUM_STEPS = 7;
	private static final int PROGRESS_INIT		= 0;
	private static final int PROGRESS_READ_X 	= 1;
	private static final int PROGRESS_READ_Y 	= 2;
	private static final int PROGRESS_READ_Z 	= 3;
	private static final int PROGRESS_WROTE_X 	= 4;
	private static final int PROGRESS_WROTE_Y 	= 5;
	private static final int PROGRESS_WROTE_Z 	= 6;
	
	
	private BranchGroupFactory shapeFactory;
	private short flags;
	private Canvas3D canvas;
	private SimpleUniverse universe;
	private BranchGroup universeGroup;
	
	public Shape3DTerrainUpdateByMaterialTypeBoundsAndRotationFactory( BranchGroupFactory shapeFactory, short flags, Canvas3D canvas ) {
		this.shapeFactory = shapeFactory;
		this.flags = flags;
		this.canvas = canvas;

		universeGroup = new BranchGroup();
		universeGroup.setCapability(BranchGroup.ALLOW_CHILDREN_EXTEND);
		universeGroup.setCapability(BranchGroup.ALLOW_CHILDREN_WRITE);
		universeGroup.setCapability(BranchGroup.ALLOW_DETACH);
		universeGroup.setCapability(BranchGroup.ENABLE_PICK_REPORTING);
		universeGroup.setPickable(true);
		universeGroup.compile();
		
		universe = new SimpleUniverse(canvas);
		universe.addBranchGraph(universeGroup);
		universe.getViewingPlatform().setNominalViewingTransform();
		
	}

	@Override
	public TerrainUpdateGroup createTerrainUpdate(
			byte materialType,
			Dimensions3D bounds, 
			Rotation rotation
	) {
		double yRotation = ((double)rotation.getDegrees()) * Math.PI / 180D;
		return new TerrainUpdateGroup( createTerrainUpdate(materialType, bounds, yRotation, null) );
	}
	
	public TerrainUpdate createTerrainUpdate(
			final byte materialType,
			Dimensions3D bounds, 
			double yRotation, 
			final OperationProgressListener progressListener
	) {
		if( progressListener != null ) {
			progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_INIT, PROGRESS_NUM_STEPS, "init")));
		}
		BranchGroup root;
		try {
			root = shapeFactory.createBranchGroup();
		} catch( Exception ex ) {
			throw new RuntimeException( "unexpected error creating terrain", ex );
		}

		// rotate the model (using above rotation)
		// scale y (z in our coordinates) so it is actually a bit shorter (fake height)
		Transform3D rotate = new Transform3D();
		rotate.rotY(yRotation);
		rotate.setScale(new Vector3d(1,TerrainConstants.DEPTH_MULTIPLIER,1));
		TransformGroup rotateGroup = new TransformGroup(rotate);
		rotateGroup.addChild(root);
		
		BranchGroup rotated = new BranchGroup();
		rotated.addChild(rotateGroup);
		
		BoundingBox boundingBox = getBounds(root, rotate);

		Point3d lower = new Point3d();
		Point3d upper = new Point3d();
		boundingBox.getLower(lower);
		boundingBox.getUpper(upper);
		double bbwidth = upper.x - lower.x;
		double bbheight = upper.y - lower.y;
		double bbdepth = upper.z - lower.z;
		
		// work out the scale
		double xscale = ((double)bounds.width - waferThickness*2)/bbwidth;
		double yscale = ((double)bounds.height - waferThickness*2)/bbheight;
		double zscale = ((double)bounds.depth - waferThickness*2)/bbdepth;
		
		final double scale = Math.min( xscale, Math.min( yscale, zscale ) );
		final double depthScale = scale * TerrainConstants.DEPTH_MULTIPLIER;
		
		// translate the model to 0,0
		Transform3D translate = new Transform3D();
//		translate.setTranslation(new Vector3d(-lower.x, -lower.y, -lower.z));
		translate.setTranslation(new Vector3d(
				-lower.x + ((double)waferThickness)/(scale),
				-lower.y + ((double)waferThickness)/(scale),
				-lower.z + ((double)waferThickness)/(scale)
		));
		TransformGroup translateGroup = new TransformGroup(translate);
		translateGroup.addChild(rotated);
		
		// scale the model
		Transform3D scale3d = new Transform3D();
		scale3d.setScale(scale);
		TransformGroup scaleGroup = new TransformGroup(scale3d);
		scaleGroup.addChild(translateGroup);
		
		
		
		BranchGroup scaled = new BranchGroup();
		scaled.addChild(scaleGroup);
		scaled.setCapability(BranchGroup.ALLOW_DETACH);
		
		// work out the (actual) model size
		int width3d = (int)Math.ceil( bbwidth * scale ) + waferThickness*2;
		int height3d = (int)Math.ceil( bbheight * scale ) + waferThickness*2;
		int depth3d = (int)Math.ceil( bbdepth * scale ) + waferThickness*2;
		
		final int width = width3d;
		final int height = depth3d;
		final int depth = height3d;
		
		final short[][][] data = new short[width][height][depth];
		
		// populate the non-culled shapes (so ones with two sided surfaces)
		
		
		// create the universe
		try {
			universeGroup.addChild(scaled);
			
			// force a render
			if( canvas.isOffScreen() ) {
				canvas.renderOffScreenBuffer();
				canvas.waitForOffScreenRendering();
			} else {
				// TODO make it visible (this doesn't work)
				TransformGroup camera = universe.getViewingPlatform().getViewPlatformTransform();
				Transform3D cameraTransform = new Transform3D();
				cameraTransform.setTranslation( new Vector3d(width/2, height/2, depth) );
				camera.setTransform( cameraTransform );
			}
	//		} else {
	//			frame = null;
	//			// seriously, we don't actually care about these values, but we need to render it before we can use the pick operations
	//			Screen3D screen = canvas.getScreen3D();
	//			screen.setSize(width, height);
	//			screen.setPhysicalScreenWidth(0.0254/90.0 * width);
	//			screen.setPhysicalScreenHeight(0.0254/90.0 * height);
	//			ImageComponent2D buffer = new ImageComponent2D(ImageComponent2D.FORMAT_RGBA, new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB));
	//			canvas.setOffScreenBuffer(buffer);
	//			canvas.renderOffScreenBuffer();
	//		}
	
			// TODO translate axes
			// note this has to be done in the AWT thread or we can get unexpected results
			Runnable r = new Runnable() {
				public void run() {
	
					// get the intersections
					PickRay ray = new PickRay();
					Point3d point = new Point3d();
					Vector3d xvector = new Vector3d(1, 0, 0);
					Vector3d yvector = new Vector3d(0, 0, -1);
					Vector3d zvector = new Vector3d(0, -1, 0);
					
					Vector3f xvectorf = new Vector3f( xvector );
					Vector3f yvectorf = new Vector3f( yvector );
					Vector3f zvectorf = new Vector3f( zvector );
					boolean empty = true;
					
					PickInfo[][][] xinfos = new PickInfo[height][depth][];
					PickInfo[][][] yinfos = new PickInfo[width][depth][];
					PickInfo[][][] zinfos = new PickInfo[width][height][];
					
					HashSet<Node> unculledNodes = new HashSet<Node>();
					
					//x
					point.x = 0;
					for( int y=height; y>0; ) {
						y--;
						point.z = height - y - 1;
						for( int z=depth; z>0; ) {
							z--;
							point.y = depth - z - 1;
							ray.set(point, xvector);
							PickInfo[] infos = universeGroup.pickAll(PickInfo.PICK_GEOMETRY, PickInfo.ALL_GEOM_INFO | PickInfo.LOCAL_TO_VWORLD | PickInfo.SCENEGRAPHPATH | PickInfo.NODE, ray);
							xinfos[y][z] = infos;
							
							// add in any missing nodes
							if( infos != null ) {
								// add in any non-culled nodes
								for( int i=infos.length; i>0; ) {
									i--;
									PickInfo info = infos[i];
									int culling = getCulling(info);
									if( culling == PolygonAttributes.CULL_NONE ) {
										unculledNodes.add( info.getNode() );
									}
								}
							}
							
						}						
					}
					if( progressListener != null ) {
						progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_READ_X, PROGRESS_NUM_STEPS, "read x")));
					}

					// y
					point.z = height;
					for( int x=width; x>0; ) {
						x--;
						point.x = x;
						for( int z=depth; z>0; ) {
							z--;
							point.y = depth - z - 1;
							ray.set(point, yvector);
							PickInfo[] infos = universeGroup.pickAll(PickInfo.PICK_GEOMETRY, PickInfo.ALL_GEOM_INFO | PickInfo.LOCAL_TO_VWORLD | PickInfo.SCENEGRAPHPATH | PickInfo.NODE, ray);
							yinfos[x][z] = infos;
							
							// add in any missing nodes
							if( infos != null ) {
								// add in any non-culled nodes
								for( int i=infos.length; i>0; ) {
									i--;
									PickInfo info = infos[i];
									int culling = getCulling(info);
									if( culling == PolygonAttributes.CULL_NONE ) {
										unculledNodes.add( info.getNode() );
									}
								}
							}
						}
					}
					if( progressListener != null ) {
						progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_READ_Y, PROGRESS_NUM_STEPS, "read y")));
					}
					
					//z
					point.y = depth;
					for( int x=width; x>0; ) {
						x--;
						point.x = x;
						for( int y=height; y>0; ) {
							y--;
							point.z = height - y - 1;
							ray.set(point, zvector);
							PickInfo[] infos = universeGroup.pickAll(PickInfo.PICK_GEOMETRY, PickInfo.ALL_GEOM_INFO | PickInfo.LOCAL_TO_VWORLD | PickInfo.SCENEGRAPHPATH | PickInfo.NODE, ray);
							zinfos[x][y] = infos;
							
							boolean air = true;
							short materialTypeId = flags;
							int z = 0;

							if( infos != null ) {
								ArrayList<Pair<PickInfo, IntersectionInfo>> sortedIntersections = new ArrayList<Pair<PickInfo, IntersectionInfo>>(infos.length * 2); 
								for( int i=infos.length; i>0; ) {
									i--;
									PickInfo info = infos[i];
									int culling = getCulling(info);
									if( culling != PolygonAttributes.CULL_NONE ) {
										IntersectionInfo[] intersections = info.getIntersectionInfos();
										for( int j=intersections.length; j>0; ) {
											j--;
											IntersectionInfo intersection = intersections[j];
											sortedIntersections.add(new Pair<PickInfo, IntersectionInfo>(info, intersection));
										}
									} else {
										unculledNodes.add(info.getNode());
									}
								}
								Collections.sort(sortedIntersections, new Comparator<Pair<PickInfo,IntersectionInfo>>() {
	
									@Override
									public int compare(
											Pair<PickInfo,IntersectionInfo> o1,
											Pair<PickInfo,IntersectionInfo> o2
									) {
										return (int)((o1.getSecond().getDistance() - o2.getSecond().getDistance())*1000);
									}
								});
								
								for( int i=0; i<sortedIntersections.size(); i++ ) {
									Pair<PickInfo,IntersectionInfo> pair = sortedIntersections.get(i);
									IntersectionInfo intersection = pair.getSecond();
									int toZ = (int)Math.round(intersection.getDistance() * depthScale);
									while( z <= toZ ) {
										data[x][y][z] = materialTypeId;
										if( !air ) {
											empty = false;
										}
										z++;
									}
									air = !air;
									if( !air ) {
										// TODO : look up material type based on the picked items appearance
										materialTypeId = (short)(materialType | flags);
									} else {
										materialTypeId = flags;
									}								
								}
							}
							if( !air ) {
								air = true;
								log.warning("terrain ended in solid at ("+x+","+y+","+z+") forced air");
							}
							materialTypeId = flags;
							while( z < depth ) {
								data[x][y][z] = materialTypeId;
								z++;
							}
						}
					}
					if( progressListener != null ) {
						progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_READ_Z, PROGRESS_NUM_STEPS, "read z")));
					}
					
					// TODO : highly inefficient
					// for every unculled node we want to add in a thin plane
					for( Node node : unculledNodes ) {
						boolean b = true;
						if( b ) {
							// x
							for( int y=0; y<height; y++ ) {
								for( int z=0; z<depth; z++ ) {
									PickInfo[] infos = xinfos[y][z];
									if( infos != null ) {
										for( int i=0; i<infos.length; i++ ) {
											PickInfo info = infos[i];
											if( info.getNode() == node ) {
												IntersectionInfo[] intersections = info.getIntersectionInfos();
												for( int j=0; j<intersections.length; j++ ) {
													// find the closest related node to the right
													IntersectionInfo intersection = intersections[j];
													IntersectionInfo east = getClosestRelatedIntersection(xinfos, y+1, z, intersection, node);
													// and to the bottom
													IntersectionInfo south = getClosestRelatedIntersection(xinfos, y, z+1, intersection, node);
													
													int minx = (int)Math.round(intersection.getDistance() * scale);
													int maxx = minx;
													if( east != null ) {
														int eastDistance = (int)Math.round(east.getDistance() * scale);
														if( eastDistance < minx ) {
															minx = eastDistance;
														} else if( eastDistance > maxx ) {
															maxx = eastDistance;
														}
													}
													if( south != null ) {
														int southDistance = (int)Math.round(south.getDistance() * scale);
														if( southDistance < minx ) {
															minx = southDistance;
														} else if( southDistance > maxx ) {
															maxx = southDistance;
														}
													}
													Geometry intersectionGeometry = intersection.getGeometry();
													if( intersectionGeometry instanceof GeometryArray ) {
														int[] intersectionVertexIndices = intersection.getVertexIndices();
														GeometryArray intersectionGeometryArray = (GeometryArray)intersectionGeometry;
														GeometryInfo intersectionGeometryInfo = new GeometryInfo(intersectionGeometryArray);
														Vector3f[] normals = intersectionGeometryInfo.getNormals();
														// TODO : are these always the same??
														float angle = 0;
														for( int k=0; k<intersectionVertexIndices.length; k++ ) {
															Vector3f normal = normals[ intersectionVertexIndices[k] ];
															angle += normal.angle(xvectorf);
														}
														angle /= intersectionVertexIndices.length;
														if( angle > Math.PI / 2 ) {
															maxx += Math.round( waferThickness * -Math.cos( angle ) );
														} else {
															minx -= Math.round( waferThickness * Math.cos( angle ) );
														}
													} else {
														minx -= waferThickness/2;
														maxx += waferThickness/2;
													}

													// populate
													for( int x = minx; x<maxx; x++ ) {
														data[x][y][z] = (short)(materialType | flags);
														empty = false;

													}
												}
											}
										}
									}								
								}
							}
							if( progressListener != null ) {
								progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_WROTE_X, PROGRESS_NUM_STEPS, "wrote x")));
							}
							
							// y
							for( int x=0; x<width; x++ ) {
								for( int z=0; z<depth; z++ ) {
									PickInfo[] infos = yinfos[x][z];
									if( infos != null ) {
										for( int i=0; i<infos.length; i++ ) {
											PickInfo info = infos[i];
											if( info.getNode() == node ) {
												IntersectionInfo[] intersections = info.getIntersectionInfos();
												for( int j=0; j<intersections.length; j++ ) {
													// find the closest related node to the right
													IntersectionInfo intersection = intersections[j];
													IntersectionInfo east = getClosestRelatedIntersection(yinfos, x+1, z, intersection, node);
													// and to the bottom
													IntersectionInfo south = getClosestRelatedIntersection(yinfos, x, z+1, intersection, node);
													
													int miny = (int)Math.round(intersection.getDistance() * scale);
													int maxy = miny;
													if( east != null ) {
														int eastDistance = (int)Math.round(east.getDistance() * scale);
														if( eastDistance < miny ) {
															miny = eastDistance;
														} else if( eastDistance > maxy ) {
															maxy = eastDistance;
														}
													}
													if( south != null ) {
														int southDistance = (int)Math.round(south.getDistance() * scale);
														if( southDistance < miny ) {
															miny = southDistance;
														} else if( southDistance > maxy ) {
															maxy = southDistance;
														}
													}
													Geometry intersectionGeometry = intersection.getGeometry();
													if( intersectionGeometry instanceof GeometryArray ) {
														int[] intersectionVertexIndices = intersection.getVertexIndices();
														GeometryArray intersectionGeometryArray = (GeometryArray)intersectionGeometry;
														GeometryInfo intersectionGeometryInfo = new GeometryInfo(intersectionGeometryArray);
														Vector3f[] normals = intersectionGeometryInfo.getNormals();
														float angle = 0;
														for( int k=0; k<intersectionVertexIndices.length; k++ ) {
															Vector3f normal = normals[ intersectionVertexIndices[k] ];
															angle += normal.angle(yvectorf);
														}
														angle /= intersectionVertexIndices.length;
														if( angle > Math.PI / 2 ) {
															maxy += Math.round( waferThickness * -Math.cos( angle ) );
														} else {
															miny -= Math.round( waferThickness * Math.cos( angle ) );
														}
													} else {
														miny -= waferThickness/2;
														maxy += waferThickness/2;
													}
													// populate
													for( int y = miny; y<maxy; y++ ) {
														data[x][y][z] = (short)(materialType | flags);
														empty = false;
													}
												}
											}
										}
									}								
								}
							}
						}
						if( progressListener != null ) {
							progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_WROTE_Y, PROGRESS_NUM_STEPS, "wrote y")));
						}
						
						// z
						for( int x=0; x<width; x++ ) {
							for( int y=0; y<height; y++ ) {
								PickInfo[] infos = zinfos[x][y];
								if( infos != null ) {
									for( int i=0; i<infos.length; i++ ) {
										PickInfo info = infos[i];
										if( info.getNode() == node ) {
											IntersectionInfo[] intersections = info.getIntersectionInfos();
											for( int j=0; j<intersections.length; j++ ) {
												// find the closest related node to the right
												IntersectionInfo intersection = intersections[j];
												IntersectionInfo east = getClosestRelatedIntersection(zinfos, x+1, y, intersection, node);
												// and to the bottom
												IntersectionInfo south = getClosestRelatedIntersection(zinfos, x, y+1, intersection, node);
												
												int minz = (int)Math.round(intersection.getDistance() * depthScale);
												int maxz = minz;
												if( east != null ) {
													int eastDistance = (int)Math.round(east.getDistance() * depthScale);
													if( eastDistance < minz ) {
														minz = eastDistance;
													} else if( eastDistance > maxz ) {
														maxz = eastDistance;
													}
												}
												if( south != null ) {
													int southDistance = (int)Math.round(south.getDistance() * depthScale);
													if( southDistance < minz ) {
														minz = southDistance;
													} else if( southDistance > maxz ) {
														maxz = southDistance;
													}
												}
												Geometry intersectionGeometry = intersection.getGeometry();
												if( intersectionGeometry instanceof GeometryArray ) {
													int[] intersectionVertexIndices = intersection.getVertexIndices();
													GeometryArray intersectionGeometryArray = (GeometryArray)intersectionGeometry;
													GeometryInfo intersectionGeometryInfo = new GeometryInfo(intersectionGeometryArray);
													Vector3f[] normals = intersectionGeometryInfo.getNormals();
													// TODO : are these always the same??
													float angle = 0;
													for( int k=0; k<intersectionVertexIndices.length; k++ ) {
														Vector3f normal = normals[ intersectionVertexIndices[k] ];
														angle += normal.angle(zvectorf);
													}
													angle /= intersectionVertexIndices.length;
													if( angle > Math.PI / 2 ) {
														maxz += Math.round( waferThickness * -Math.cos( angle ) );
													} else {
														minz -= Math.round( waferThickness * Math.cos( angle ) );
													}
												} else {
													minz -= waferThickness/2;
													maxz += waferThickness/2;
												}
												// populate
												for( int z = minz; z<maxz; z++ ) {
													empty = false;
													data[x][y][z] = (short)(materialType | flags);
												}
											}
										}
									}
								}
							}
						}
					}
					if( progressListener != null ) {
						progressListener.progressUpdated( new OperationProgressEvent(new OperationProgress(PROGRESS_WROTE_Z, PROGRESS_NUM_STEPS, "wrote z")));
					}
					
					if( empty ) {
						log.warning("created empty model");
					}
				}
			};
			// seems to require to be done in the AWT thread, even if there isn't any AWT component involved?!
			if( true || SwingUtilities.isEventDispatchThread() ) {
				r.run();
			} else {
				try {
					SwingUtilities.invokeAndWait(r);
				} catch( Exception ex ) {
					throw new RuntimeException( "unable to invoke swing thread", ex );
				}
			}
		} finally {
			universeGroup.removeChild(scaled);
		}
		
		// create a terrain update		
		return new TerrainUpdate( data, width, height, depth);
	}
	
	private int getCulling( PickInfo info ) {
		// TODO : check against surface normal to make sure it's pointing the right way
		int culling;
		if( info != null ) {
			Shape3D node = (Shape3D)info.getNode();
			if( node != null ) {
				Appearance appearance = node.getAppearance();
				if( appearance != null ) {
					PolygonAttributes polyAttributes = appearance.getPolygonAttributes();
					if( polyAttributes != null ) {
						culling = polyAttributes.getCullFace();
					} else {
						culling = PolygonAttributes.CULL_NONE;
					}
				} else {
					culling = PolygonAttributes.CULL_NONE;
				}
			} else {
				culling = PolygonAttributes.CULL_NONE;
			}
		} else { 
			culling = PolygonAttributes.CULL_NONE;
		}
		return culling;
	}
	
	private IntersectionInfo getClosestRelatedIntersection( PickInfo[][][] infos, int a, int b, IntersectionInfo with, Node node ) {
		IntersectionInfo result;
		if( infos.length > a ) {
			result = null;
		} else if( infos[a].length > b ) {
			result = null;	
		} else {
			int[] withIndexes = with.getVertexIndices();
			GeometryInfo withga = new GeometryInfo( (GeometryArray)with.getGeometry() );
			Point3f[] withVertexes = new Point3f[withIndexes.length];
			for( int i=0; i<withVertexes.length; i++ ) {
				Point3f p;
				p = withga.getCoordinates()[withIndexes[i]];
				withVertexes[i] = p; 
			}
			PickInfo[] testInfos = infos[a][b];
			if( testInfos != null ) {
				result = null;
				for( int i=0; i<testInfos.length; i++ ) {
					PickInfo testInfo = testInfos[i];
					if( testInfo.getNode() == node ) {
						IntersectionInfo[] testIntersections = testInfo.getIntersectionInfos();
						for( int j=0; j<testIntersections.length; j++ ) {
							IntersectionInfo testIntersection = testIntersections[j];
							int[] testIndexes = testIntersection.getVertexIndices();
							// has to share at least two (or should that be one?) indexes
							int common = 0;
							boolean joined = false;
							GeometryInfo testga = new GeometryInfo( (GeometryArray)testIntersection.getGeometry() );
							// TODO better matching (match along the lines, not the points)
							outer: for( int k=withVertexes.length; k>0; ) {
								k--;
								Point3f withVertex = withVertexes[k];
								
								for( int l=testIndexes.length; l>0; ) {
									l--;
									int testIndex = testIndexes[l];
									Point3f testVertex = testga.getCoordinates()[testIndex];
									if( testVertex.equals(withVertex) ) {
										common++;
										if( common >= MIN_COMMON_VERTEXES ) {
											joined = true;
											break outer;
										}
									}
								}
								if( joined ) {
									if( result == null || Math.abs( result.getDistance() - with.getDistance() ) > Math.abs( testIntersection.getDistance() - with.getDistance() ) ) {
										result = testIntersection;
									}
								}
							}
						}
					}
				}
			} else {
				result = null;
			}
		}
		return result;
	}
	
	public BoundingBox getBounds( SceneGraphObject sgo, Transform3D transform ) {
		if( sgo instanceof BranchGroup ) {
			return getBounds( (BranchGroup)sgo, transform );
		} else if( sgo instanceof Shape3D ) {
			return getBounds( (Shape3D)sgo, transform );
		} else if( sgo instanceof GeometryArray ) {
			return getBounds( (GeometryArray)sgo, transform );
		} else if( sgo instanceof Node ) {
			// rough bounds (assume the sgo is already transformed)
			Bounds boundingObject = ((Node)sgo).getBounds();
			BoundingBox boundingBox;
			if( boundingObject instanceof BoundingBox ) {
				boundingBox = (BoundingBox)boundingObject;			
			} else {
				boundingBox = new BoundingBox( boundingObject );
			}
			return boundingBox;
		} else {
			throw new RuntimeException( "unexpected class "+sgo.getClass().getName() );
		}
	}
	
	@SuppressWarnings("unchecked")
	public BoundingBox getBounds( BranchGroup bg, Transform3D transform ) {
		BoundingBox result = null;
		Enumeration<SceneGraphObject> children = bg.getAllChildren();
		while( children.hasMoreElements() ) {
			BoundingBox childResult = getBounds( children.nextElement(), transform );
			if( childResult != null ) {
				if( result == null ) {
					result = childResult;
				} else {
					result.combine(childResult);
				}
			}
		}
		return result;
	}
	
	@SuppressWarnings("unchecked")
	public BoundingBox getBounds( Shape3D shape, Transform3D transform ) {
		BoundingBox result = null;
		Enumeration<Geometry> geometries = shape.getAllGeometries();
		while( geometries.hasMoreElements() ) {
			Geometry geometry = geometries.nextElement();
			BoundingBox geometryBounds = getBounds( geometry, transform );
			if( geometryBounds != null ) {
				if( result == null ) {
					result = geometryBounds;
				} else {
					result.combine(geometryBounds);
				}
			}
		}
		return result;
	}
	
	public BoundingBox getBounds( GeometryArray geometry, Transform3D transform ) {
		Point3f min = null;
		Point3f max = null;
		GeometryInfo info = new GeometryInfo( geometry );
		Point3f[] coordinates = info.getCoordinates();
		for( int i=coordinates.length; i>0; ) {
			i--;
			Point3f coordinate = new Point3f( coordinates[i] );
			transform.transform(coordinate);
			if( min == null ) {
				 min = new Point3f( coordinate );
			} else {
				if( coordinate.x < min.x ) {
					min.x = coordinate.x;
				}
				if( coordinate.y < min.y ) {
					min.y = coordinate.y;
				}
				if( coordinate.z < min.z ) {
					min.z = coordinate.z;
				}
			}
			if( max == null ) {
				max = new Point3f( coordinate );
			} else {
				if( coordinate.x > max.x ) {
					max.x = coordinate.x;
				}
				if( coordinate.y > max.y ) {
					max.y = coordinate.y;
				}
				if( coordinate.z > max.z ) {
					max.z = coordinate.z;
				}
			}
		}
		if( min != null && max != null ) {
			return new BoundingBox( new Point3d( min ), new Point3d( max ) );
		} else {
			return null;
		}
	}
}
